home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / dev / c / vbcc.lha / vbcc / flow.c < prev    next >
C/C++ Source or Header  |  1997-12-30  |  22KB  |  527 lines
  1. /*  $VER: vbcc (flow.c) V0.4     */
  2. /*  Generierung des FLussgraphs und Optimierungen des Kontrollflusses   */
  3.  
  4. #include "opt.h"
  5.  
  6. static char FILE_[]=__FILE__;
  7.  
  8. int bvcmp(unsigned char *dest,unsigned char *src,size_t len)
  9. /*  vergleicht zwei Bitvektoren    */
  10. {
  11.     for(;len>0;len--)
  12.         if(*dest++!=*src++) return(0);
  13.     return(1);
  14. }
  15. void bvunite(unsigned char *dest,unsigned char *src,size_t len)
  16. /*  berechnet Vereinigung zweier Bitvektoren    */
  17. {
  18.     for(;len>0;len--)
  19.         *dest++|=*src++;
  20. }
  21. void bvintersect(unsigned char *dest,unsigned char *src,size_t len)
  22. /*  berechnet Durchschnitt zweier Bitvektoren   */
  23. {
  24.     for(;len>0;len--)
  25.         *dest++&=*src++;
  26. }
  27. void bvdiff(unsigned char *dest,unsigned char *src,size_t len)
  28. /*  berechnet 'Differenz' zweier Bitvektoren    */
  29. {
  30.     for(;len>0;len--)
  31.         *dest++&=~(*src++);
  32. }
  33.  
  34. unsigned int basic_blocks;
  35.  
  36. struct flowgraph *construct_flowgraph(void)
  37. /*  entfernt ueberfluessige Labels und erzeugt Flussgraph   */
  38. {
  39.     struct IC *p;
  40.     int firstl=lastlabel,lcnt=label-firstl,currentl,i,code,l;
  41.     int *iseq=mymalloc(lcnt*sizeof(int));
  42.     int *used=mymalloc(lcnt*sizeof(int));
  43.     struct flowgraph **lg=mymalloc(lcnt*sizeof(struct flowgraph *));
  44.     struct flowgraph *g=mymalloc(sizeof(struct flowgraph)),*fg=g;
  45.     g->start=first_ic;g->in=0;g->branchout=0;g->loopend=0;
  46.  
  47.     for(i=0;i<lcnt;i++) {iseq[i]=used[i]=0;lg[i]=0;}
  48.     currentl=0;firstl++;
  49.     /*  Diese Schleife entfernt alle Labels, die mit anderen    */
  50.     /*  uebereinstimmen, merkt sich das und kennzeichnet alle   */
  51.     /*  Labels, die benutzt werden.                             */
  52.     /*  Ausserdem wird der Flussgraph teilweise aufgebaut.      */
  53.     if(DEBUG&1024) {puts("construct_flowgraph(): loop1");/*scanf("%d",&i);*/}
  54.     i=1;g->index=i;
  55.     for(p=first_ic;p;){
  56.         code=p->code;
  57.         if(code>=BEQ&&code<=BRA){
  58.             l=p->typf;
  59.             /*  als used markieren; falls aequivalent, das erste markieren  */
  60.             if(iseq[l-firstl]) used[iseq[l-firstl]-firstl]=1;
  61.                 else           used[l-firstl]=1;
  62.             /*  Flussgraph beenden und evtl. naechsten Knoten erzeugen  */
  63.             g->end=p;
  64.             if(p->next){
  65.                 g->normalout=mymalloc(sizeof(struct flowgraph));
  66.                 g->normalout->in=mymalloc(sizeof(struct flowlist));
  67.                 g->normalout->in->next=0;
  68.                 g->normalout->in->graph=g;
  69.                 g=g->normalout;
  70.                 g->start=p->next;
  71.                 g->branchout=0;
  72.                 g->loopend=0;
  73.                 g->index=++i;
  74.             }else g->normalout=0;
  75.  
  76.             currentl=0;p=p->next;continue;
  77.         }
  78.         if(code==ALLOCREG||code==FREEREG){p=p->next; continue;}
  79.         if(code!=LABEL){currentl=0;p=p->next;continue;}
  80.         /*  ist ein Label   */
  81.         l=p->typf;
  82.         if(currentl){
  83.         struct IC *m;
  84.             iseq[l-firstl]=currentl;
  85.             if(used[l-firstl]) used[currentl-firstl]=1;
  86.         m=p;p=p->next;
  87.             remove_IC(m);
  88.         continue;
  89. /*            if(DEBUG&1024) printf("label %d==%d\n",l,iseq[l-firstl]);*/
  90.         }else{
  91.             currentl=l;
  92.             if(g->start!=p){
  93.                 g->end=p->prev;
  94.                 g->normalout=mymalloc(sizeof(struct flowgraph));
  95.                 g->normalout->in=mymalloc(sizeof(struct flowlist));
  96.                 g->normalout->in->next=0;
  97.                 g->normalout->in->graph=g;
  98.                 g=g->normalout;
  99.                 g->start=p;
  100.                 g->branchout=0;
  101.                 g->loopend=0;
  102.                 g->index=++i;
  103.             }else g->branchout=0;
  104.             lg[l-firstl]=g;
  105.         }
  106.     p=p->next;
  107.     }
  108.     g->end=last_ic;g->normalout=g->branchout=0;
  109.     if(DEBUG&1024) printf("%d basic blocks\n",i);
  110.     basic_blocks=i;
  111.  
  112. /*    if(DEBUG&1024) for(i=firstl;i<=lcnt;i++) printf("L%d used: %d\n",i,used[i-firstl]);*/
  113.     /*  Diese Schleife entfernt alle nicht benutzten Labels und biegt alle  */
  114.     /*  Branches auf aequivalente Labels um.                                */
  115.     if(DEBUG&1024) {puts("construct_flowgraph(): loop2");/*scanf("%d",&i);*/}
  116.     g=fg;
  117.     while(g){
  118.         int flag=0;struct flowlist *lp;
  119. /*        printf("g=%p\n",(void *)g);*/
  120.         g->av_in=g->av_out=g->av_gen=g->av_kill=0;
  121.         g->rd_in=g->rd_out=g->rd_gen=g->rd_kill=0;
  122.         g->ae_in=g->ae_out=g->ae_gen=g->ae_kill=0;
  123.         g->cp_in=g->cp_out=g->cp_gen=g->cp_kill=0;
  124.         p=g->start;
  125.         while(p&&!flag){
  126. /*            pric2(stdout,p);*/
  127.             code=p->code;
  128.             if(code>=BEQ&&code<=BRA){
  129.                 l=p->typf;
  130.                 if(iseq[l-firstl]) p->typf=l=iseq[l-firstl];
  131.                 /*  in Flussgraph eintragen */
  132.                 g->branchout=lg[l-firstl];
  133.                 if(!lg[l-firstl]) ierror(0);
  134.                 lp=lg[l-firstl]->in;
  135.                 /*  das hier sollte man noch schoener machen    */
  136.                 if(!lp){
  137.                     lg[l-firstl]->in=mymalloc(sizeof(struct flowlist));
  138.                     lg[l-firstl]->in->next=0;
  139.                     lg[l-firstl]->in->graph=g;
  140.                 }else{
  141.                     while(lp&&lp->next) lp=lp->next;
  142.                     lp->next=mymalloc(sizeof(struct flowlist));
  143.                     lp->next->next=0;
  144.                     lp->next->graph=g;
  145.                 }
  146.             }
  147. /*            if(code==LABEL&&!used[p->typf-firstl]) remove_IC(p);*/
  148.             if(p==g->end) flag=1;
  149.             p=p->next;
  150.         }
  151.         g=g->normalout;
  152.     }
  153.     /*  Unbenutzte Labels entfernen und Bloecke verbinden   */
  154.     if(DEBUG&1024) {puts("construct_flowgraph(): loop3");/*scanf("%d",&i);*/}
  155.     for(g=fg;g;g=g->normalout){
  156.         if(g->end&&(g->end->code<BEQ||g->end->code>BRA)){
  157.             struct flowgraph *next=g->normalout;struct flowlist *lp;
  158.             if(next&&next->start&&next->start->code==LABEL&&!used[next->start->typf-firstl]){
  159.                 if(next->end!=next->start) g->end=next->end;
  160.                 g->normalout=next->normalout;
  161.                 g->branchout=next->branchout;
  162.                 free(next->in); /*  darf eigentlich nur einen Vorgaenger haben  */
  163.                 /*  in im Nachfolgeknoten auf den ersten der beiden setzen  */
  164.                 if(next->normalout&&next->normalout->in) next->normalout->in->graph=g;
  165.                 /*  in im Ziel von next->branchout auf den ersten setzen    */
  166.                 if(next->branchout){
  167.                     lp=next->branchout->in;
  168.                     while(1){
  169.                         if(lp->graph==next){ lp->graph=g;break;}
  170.                         lp=lp->next;if(!lp) ierror(0);
  171.                     }
  172.                 }
  173.                 if(DEBUG&1024){ printf("unused label deleted:\n");pric2(stdout,next->start);}
  174.                 remove_IC(next->start);
  175.                 free(next);
  176.             }
  177.         }
  178.         /*  unbenutzte Labels entfernen */
  179.         if(g->start&&g->start->code==LABEL&&!used[g->start->typf-firstl])
  180.             remove_IC_fg(g,g->start);
  181.     }
  182.     free(iseq);
  183.     free(used);
  184.     return(fg);
  185. }
  186.  
  187. void print_flowgraph(struct flowgraph *g)
  188. /*  Gibt Flussgraph auf Bildschirm aus  */
  189. {
  190.     static int dontprint=0;
  191.     int flag,i;struct flowlist *lp;struct IC *ip;
  192.     if(dontprint) return;
  193.     puts("print_flowgraph()");scanf("%d",&i);
  194.     if(i<0){dontprint=1;return;}
  195.     if(!i) return;
  196.     while(g){
  197.         printf("\nBasic Block nr. %d\n",g->index);
  198.         printf("\tin from ");
  199.         lp=g->in;
  200.         while(lp){if(lp->graph) printf("%d ",lp->graph->index);lp=lp->next;}
  201.         printf("\n\tout to %d %d\n",g->normalout?g->normalout->index:0,g->branchout?g->branchout->index:0);
  202.         if(g->loopend) printf("head of a loop ending at block %d\n",g->loopend->index);
  203.         if(i&2){
  204.             printf("av_gen:\n"); print_av(g->av_gen);
  205.             printf("av_kill:\n"); print_av(g->av_kill);
  206.             printf("av_in:\n"); print_av(g->av_in);
  207.             printf("av_out:\n"); print_av(g->av_out);
  208.         }
  209.         if(i&4){
  210.             printf("rd_gen:\n"); print_rd(g->rd_gen);
  211.             printf("rd_kill:\n"); print_rd(g->rd_kill);
  212.             printf("rd_in:\n"); print_rd(g->rd_in);
  213.             printf("rd_out:\n"); print_rd(g->rd_out);
  214.